/*************************************************************************
	> File Name: priority_queue.cpp
	> Author: zhangxu
	> Mail: 
	> Created Time: 二  8/20 12:57:02 2024
 ************************************************************************/

// #include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <cstdio>
#define ROOT 1
#define CMP >
#define FATHER(i) ((i) / 2)
#define LEFT(i)   ((i) * 2)
#define RIGHT(i)  ((i) * 2 + 1)
#define swap(a, b) { \
	__typeof(a) __c = (a); \
	(a) = (b); \
	(b) = __c; \
}

typedef struct PriorityQueue {
	int *__data, *data;
	int size, cnt;
} PQ;

PQ *initPQ(int size) {
	PQ *p = (PQ *)malloc(sizeof(PQ));
	p->__data = (int *)malloc(sizeof(int) * size);
	p->data = p->__data - ROOT;
	p->size = size;
	p->cnt = 0;
	return p;
}

int top(PQ *p) {
	return p->data[ROOT];
}

bool isEmpty(PQ *p) {
	return p->cnt == 0;
}

bool isFull(PQ *p) {
	return p->cnt == p->size;
}

void upMaintain(int *data, int i) {
	while(i > ROOT && data[i] CMP data[FATHER(i)]) {
		swap(data[i], data[FATHER(i)]);
		i = FATHER(i);
	}
	return ;
}

void downMaintain(int *data, int i, int n) {
	while(LEFT(i) <= n) {
		int ind = i, l = LEFT(i), r = RIGHT(i);
		if(data[l] CMP data[ind]) ind = l;
		if(r <= n && data[r] CMP data[ind]) ind = r;
		if(ind == i) break;
		swap(data[i], data[ind]);
		i = ind;
	}
	return ;
}

bool push(PQ *p, int val) {
	if(isFull(p)) return false;
	p->cnt += 1;
	p->data[p->cnt] = val;
	upMaintain(p->data, p->cnt);
	return true;
}

bool pop(PQ *p) {
	if(isEmpty(p)) return false;
	p->data[ROOT] = p->data[p->cnt];
	p->cnt -= 1;
	downMaintain(p->data, ROOT, p->cnt);
	return true;
}

void outPut(PQ *p) {
	int len = 0;
	for(int i = 1; i <= p->cnt; i++) {
		len += printf("%3d", i);
	}
	printf("\n");
	for(int i = 0; i < len; i++) {
		printf("-");
	}
	printf("\n");
	for(int i = 1; i <= p->cnt; i++) {
		printf("%3d", p->data[i]);
	}
	printf("\n");
}

void clearPQ(PQ *p) {
	if(p == NULL) return ;
	free(p->__data);
	free(p);
	return ;
}
#define MAX_N 100
#define MAX_OP 10

int main() {
	srand(time(0));
	PQ *p = initPQ(MAX_N);
	int n = MAX_OP, val;
	while(n--) {
		val = rand() % 100;
		push(p, val);
	}
	outPut(p);
	printf("\n");
	pop(p);
	outPut(p);
	printf("\n");
	pop(p);
	outPut(p);
	printf("\n");
	clearPQ(p);
	return 0;
}